package week6;

/**
 *
 * 64. 最小路径和
 * https://leetcode-cn.com/problems/minimum-path-sum/
 *
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：2 ms, 在所有 Java 提交中击败了97.43% 的用户
 * 内存消耗：41 MB, 在所有 Java 提交中击败了75.45% 的用户
 * 通过测试用例：61 / 61
 * 炫耀一下:
 *
 *
 */
public class Week6MinimumPathSum {

    public int minPathSum(int[][] grid) {
        int minPathSum = 0;
        if(grid == null || grid.length == 0 || grid[0].length == 0) {
            // 空数组 直接返回0 不处理
        } else {
            int rowLength = grid.length;
            int columnLength = grid[0].length;
            int[][] dynamicPlan = new int[rowLength][columnLength];
            dynamicPlan[0][0] = grid[0][0];
            for(int rowSize = 1; rowSize < rowLength; rowSize++) {
                // 使用 首列值初始化
                dynamicPlan[rowSize][0] = dynamicPlan[rowSize - 1][0] + grid[rowSize][0];
            }
            for(int columnSize = 1; columnSize < columnLength; columnSize++) {
                // 使用 首行值初始化
                dynamicPlan[0][columnSize] = dynamicPlan[0][columnSize - 1] + grid[0][columnSize];
            }
            for(int rowSize = 1; rowSize < rowLength; rowSize++) {
                for(int columnSize = 1; columnSize < columnLength; columnSize++) {
                    // 任意单元格最小值 = min(上面一个最小值, 左面一个最小值) + 当前单元格的值
                    dynamicPlan[rowSize][columnSize] = Math.min(dynamicPlan[rowSize - 1][columnSize], dynamicPlan[rowSize][columnSize - 1]) + grid[rowSize][columnSize];
                }
            }

            minPathSum = dynamicPlan[rowLength - 1][columnLength - 1];
        }

        return minPathSum;
    }
}
